package com.example.offer.no0024.impl;

import java.util.ArrayList;
import java.util.List;

import com.example.offer.no0024.ListNode;
import com.example.offer.no0024.Solution;

/**
 * @author yumuhui <yumuhui@kuaishou.com>
 * 时间复杂度：O(n)，其中 n 是链表的长度。需要对链表的每个节点进行反转操作。
 * 空间复杂度：O(n)，其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间，最多为 n 层。
 * Created on 2021-05-13
 */
public class RecurSolutionImpl implements Solution {
    @Override
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}
